package gold.digger;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC765 {
    public long startExecuteTime = System.currentTimeMillis();

    /*
     * @param 此题目参考了别人代码
     * 这是因为问题情况较为复杂
     * 未来需要再次复习此道题目
     * 好家伙，真老伙计
     * @return:
     */

//    此处撰写解题思路
//    将每队情侣的编号(0,1)(2,3)(4,5)...除以2得到(0,0)(1,1)(2,2)...
//    这样相同编号代表是一对情侣
//    遍历人员，将每张沙发上的两个人员编号union一下，如果本来编号就相同，则表示两个人是一类
//    若一张沙发上两个人编号不同，则将这两个人的编号并集到同一个类别中，由于这两个人都分别有自己的对象，所以在后续的遍历中另外两个对象和他们沙发上的另一个人都会被并到同一个集合中，最终会形成一个闭环，如(0,1)(1,3)(2,0)(3,2)
//    每一个闭环若有k张沙发，则需要交换k-1次，而在一个闭环中只有根节点root满足parent[root] == root
//    所以最后得到的parent数组中parent[i] != i的个数就是最终需要交换的次数

    class Solution {

        private class UnionFind {
            int[] parent;
            int[] weight;

            UnionFind(int[] row) {
                int m = row.length / 2;
                parent = new int[m];
                weight = new int[m];
                for (int i = 0; i < m; i++) {
                    parent[i] = i;
                    weight[i] = 1;
                }
            }

            public int find(int x) {
                if (parent[x] != x) parent[x] = find(parent[x]);
                return parent[x];
            }

            public void union(int x, int y) {
                int rootx = find(x);
                int rooty = find(y);
                if (rootx == rooty) return;
                if (weight[rootx] > weight[rooty]) {
                    parent[rooty] = rootx;
                    weight[rootx] += weight[rooty];
                } else {
                    parent[rootx] = rooty;
                    weight[rooty] += weight[rootx];
                }
            }

            public int getRet() {
                int ret = 0;
                for (int i = 0; i < parent.length; i++) {
                    if (parent[i] != i) ret++;
                }
                return ret;
            }
        }

        public int minSwapsCouples(int[] row) {
            UnionFind uf = new UnionFind(row);
            for (int i = 0; i < row.length; i += 2) {
                uf.union(row[i] / 2, row[i + 1] / 2);
            }
            return uf.getRet();
        }
    }


    class Solution_Greedy {
        public int minSwapsCouples(int[] row) {
            int ans = 0;
            for (int i = 0; i < row.length; i += 2) {
                int x = row[i];
                if (row[i + 1] == (x ^ 1)) continue;
                ans++;
                for (int j = i + 1; j < row.length; ++j) {
                    if (row[j] == (x ^ 1)) {
                        row[j] = row[i + 1];
                        row[i + 1] = x ^ 1;
                        break;
                    }
                }
            }
            return ans;
        }
    }

    public void run() {
        Solution solution = new Solution();
        List<Integer> list = new ArrayList<>();
        System.out.println(solution.toString());
    }

    public static void main(String[] args) throws Exception {
        LC765 an = new LC765();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
